import java.math.BigInteger;

//025. 一千位斐波那契数
//        斐波那契数列定义如下：Fn=Fn−1+Fn−2，其中 F1=1,F2=1
//        前 12 个斐波那契数分别为：1,1,2,3,5,8,13,21,34,55,89,144。其中第 12 个是第一个包含
//        三位数的斐波那契数。
//        求斐波那契数列中第一个包含 1000 位数字的项是第几项？
//        答案：4782
public class Week025 {
    static final int NUM = 1000;

    static void run() {
        if (NUM == 0) {
            System.out.println("ERROR");
            return;
        }
        if (NUM == 1) {
            System.out.println("1");
            return;
        }
        BigInteger[] fib = new BigInteger[3];
        fib[1] = fib[2] = BigInteger.ONE;
        for (int cur = 3; true; ++cur) {
            fib[cur % 3] = fib[(cur - 1) % 3].add(fib[(cur - 2) % 3]);
            if (fib[cur % 3].toString().length() >= NUM) {
                System.out.println(cur);
                return;
            }
        }
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
